﻿﻿#define _CRT_SECURE_NO_WARNINGS 1
//给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
//
//你不需要 保留 每个分区中各节点的初始相对位置。
//
//
//
//示例 1：
//
//
//输入：head = [1, 4, 3, 2, 5, 2], x = 3
//输出：[1, 2, 2, 4, 3, 5]
//示例 2：
//
//输入：head = [2, 1], x = 2
//输出：[1, 2]
//
//
//提示：
//
//链表中节点的数目在范围[0, 200] 内
//- 100 <= Node.val <= 100
//- 200 <= x <= 200
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/partition-list-lcci
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


    struct ListNode* partition(struct ListNode* head, int x) {
    struct ListNode* less = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* large = (struct ListNode*)malloc(sizeof(struct ListNode));
    less->next = large->next = NULL;
    struct ListNode* cur = head;
    struct ListNode* lesstail = less;// tail指针应该指向当前链表的最后一个节点 才可以去方便链接下一个节点
    struct ListNode* largetail = large; //故不能采用lesstail=less->next的这种赋值，这样导致lesstail指向
                                   //的不是最后一个节点，而是最后一个节点之后的空
    if (cur == NULL)
        return head;
    else
    {
        while (cur)
        {
            if (cur->val < x)
            {
                lesstail->next = cur;
                lesstail = lesstail->next;
            }
            else
            {
                largetail->next = cur;
                largetail = largetail->next;
            }
            cur = cur->next;
        }
        largetail->next = NULL;//很重要，不置空可能造成环形链表
        lesstail->next = large->next;
        head = less->next;
        free(less);
        free(large);
        less = large = NULL;
        return head;
    }


}
